///\todo upgrade

//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_IMAGE_RASTERIZER_CCELLRASTERIZER_H_
#define _BUOLA_IMAGE_RASTERIZER_CCELLRASTERIZER_H_

#include <buola/image.h>

namespace buola { namespace img {

static const int cPolySubpixelShift=8;
static const int cPolySubpixelScale=1<<cPolySubpixelShift;
static const int cPolySubpixelMask=cPolySubpixelScale-1;
    
template<typename tCell>
class CCellRasterizer
{
    static const int cCellBlockShift=12;
    static const int cCellBlockSize=1<<cCellBlockShift;
    static const int cCellBlockMask=cCellBlockSize-1;
    static const int cCellBlockPool=256;
    static const int cCellBlockLimit=1024;

    struct SSortedY
    {
        int mStart;
        int mNum;
    };

public:
    typedef tCell TCell;

    CCellRasterizer();
    CCellRasterizer(const CCellRasterizer&)=delete;

    ~CCellRasterizer();

    CCellRasterizer& operator=(const CCellRasterizer&)=delete;
    
    void Reset();
    void Style(const tCell &pStyleCell);
    void Line(int x1, int y1, int x2, int y2);

    int MinX() const { return mMinX; }
    int MinY() const { return mMinY; }
    int MaxX() const { return mMaxX; }
    int MaxY() const { return mMaxY; }

    void SortCells();

    size_t TotalCells() const                   {   return mNumCells;   }
    size_t ScanlineCellCount(int y) const       {   return mSortedY[y-mMinY].mNum;  }

    tCell *const *ScanlineCells(int y) const     {   return mSortedCells.data()+mSortedY[y-mMinY].mStart;    }

    bool Sorted() const { return mSorted; }

private:
    void SetCurCell(int x,int y);
    void AddCurCell();
    void RenderHLine(int ey, int x1, int y1, int x2, int y2);
    void AllocateBlock();

private:
    std::vector<tCell*> mBlocks;
    size_t mNextBlock;
    size_t mNumCells;
    tCell *mCurCellPtr;
    std::vector<tCell*> mSortedCells;
    std::vector<SSortedY> mSortedY;
    tCell mCurCell;
    tCell mStyleCell;
    int mMinX,mMinY,mMaxX,mMaxY;
    bool mSorted;
};

template<typename tCell>
CCellRasterizer<tCell>::CCellRasterizer()
    :   mNextBlock(0)
    ,   mNumCells(0)
    ,   mCurCellPtr(nullptr)
    ,   mMinX(0x7FFFFFFF)
    ,   mMinY(0x7FFFFFFF)
    ,   mMaxX(-0x7FFFFFFF)
    ,   mMaxY(-0x7FFFFFFF)
    ,   mSorted(false)
{
    mBlocks.reserve(cCellBlockPool);
    mStyleCell.Initial();
    mCurCell.Initial();
}

template<typename tCell>
CCellRasterizer<tCell>::~CCellRasterizer()
{
    ///\todo consider using something similar to pod_allocator in AGG
    for(tCell *lBlock : mBlocks)
        delete[] lBlock;
}

template<typename tCell>
void CCellRasterizer<tCell>::Reset()
{
    mNextBlock=0;
    mNumCells=0;
    mStyleCell.Initial();
    mCurCell.Initial();
    mMinX=0x7FFFFFFF;
    mMinY= 0x7FFFFFFF;
    mMaxX=-0x7FFFFFFF;
    mMaxY=-0x7FFFFFFF;
    mSorted=false;
}

template<typename tCell>
inline void CCellRasterizer<tCell>::AddCurCell()
{
    if(mCurCell.mArea|mCurCell.mCover)
    {
        if((mNumCells&cCellBlockMask)==0)
            AllocateBlock();
        *(mCurCellPtr++)=mCurCell;
        ++mNumCells;
    }
}

template<typename tCell>
inline void CCellRasterizer<tCell>::SetCurCell(int x,int y)
{
    if(mCurCell.NotEqual(x, y, mStyleCell))
    {
        AddCurCell();
        mCurCell.Style(mStyleCell);
        mCurCell.x=x;
        mCurCell.y=y;
        mCurCell.mCover=0;
        mCurCell.mArea=0;
    }
}

template<typename tCell>
inline void CCellRasterizer<tCell>::RenderHLine(int ey,int x1, int y1,int x2, int y2)
{
    int ex1 = x1 >> cPolySubpixelShift;
    int ex2 = x2 >> cPolySubpixelShift;
    int fx1 = x1 & cPolySubpixelMask;
    int fx2 = x2 & cPolySubpixelMask;

    int delta, p, first, dx;
    int incr, lift, mod, rem;

    //trivial case. Happens often
    if(y1 == y2)
    {
        SetCurCell(ex2, ey);
        return;
    }

    //everything is located in a single cell.  That is easy!
    if(ex1 == ex2)
    {
        delta = y2 - y1;
        mCurCell.mCover+=delta;
        mCurCell.mArea+=(fx1 + fx2) * delta;
        return;
    }

    //ok, we'll have to render a run of adjacent cells on the same
    //hline...
    p     = (cPolySubpixelScale - fx1) * (y2 - y1);
    first = cPolySubpixelScale;
    incr  = 1;

    dx = x2 - x1;

    if(dx < 0)
    {
        p     = fx1 * (y2 - y1);
        first = 0;
        incr  = -1;
        dx    = -dx;
    }

    delta = p / dx;
    mod   = p % dx;

    if(mod < 0)
    {
        delta--;
        mod += dx;
    }

    mCurCell.mCover += delta;
    mCurCell.mArea  += (fx1 + first) * delta;

    ex1 += incr;
    SetCurCell(ex1, ey);
    y1  += delta;

    if(ex1 != ex2)
    {
        p     = cPolySubpixelScale * (y2 - y1 + delta);
        lift  = p / dx;
        rem   = p % dx;

        if (rem < 0)
        {
            lift--;
            rem += dx;
        }

        mod -= dx;

        while (ex1 != ex2)
        {
            delta = lift;
            mod  += rem;
            if(mod >= 0)
            {
                mod -= dx;
                delta++;
            }

            mCurCell.mCover += delta;
            mCurCell.mArea  += cPolySubpixelScale * delta;
            y1  += delta;
            ex1 += incr;
            SetCurCell(ex1, ey);
        }
    }
    delta = y2 - y1;
    mCurCell.mCover += delta;
    mCurCell.mArea  += (fx2 + cPolySubpixelScale - first) * delta;
}

template<typename tCell>
inline void CCellRasterizer<tCell>::Style(const tCell &pStyleCell)
{
    mStyleCell.Style(pStyleCell);
}

template<typename tCell>
void CCellRasterizer<tCell>::Line(int x1, int y1, int x2, int y2)
{
    static const int cDXLimit=16384 << cPolySubpixelShift;

    int dx = x2 - x1;

    if(dx >= cDXLimit || dx <= -cDXLimit) //subdivide too long lines... why??
    {
        int cx = (x1 + x2) >> 1;
        int cy = (y1 + y2) >> 1;
        Line(x1, y1, cx, cy);
        Line(cx, cy, x2, y2);
    }

    int dy = y2 - y1;
    int ex1 = x1 >> cPolySubpixelShift;
    int ex2 = x2 >> cPolySubpixelShift;
    int ey1 = y1 >> cPolySubpixelShift;
    int ey2 = y2 >> cPolySubpixelShift;
    int fy1 = y1 & cPolySubpixelMask;
    int fy2 = y2 & cPolySubpixelMask;

    int x_from, x_to;
    int p, rem, mod, lift, delta, first, incr;

    if(ex1 < mMinX) mMinX = ex1;
    if(ex1 > mMaxX) mMaxX = ex1;
    if(ey1 < mMinY) mMinY = ey1;
    if(ey1 > mMaxY) mMaxY = ey1;
    if(ex2 < mMinX) mMinX = ex2;
    if(ex2 > mMaxX) mMaxX = ex2;
    if(ey2 < mMinY) mMinY = ey2;
    if(ey2 > mMaxY) mMaxY = ey2;

    SetCurCell(ex1, ey1);

    //everything is on a single hline
    if(ey1 == ey2)
    {
        RenderHLine(ey1, x1, fy1, x2, fy2);
        return;
    }

    //Vertical line - we have to calculate start and end cells,
    //and then - the common values of the area and coverage for
    //all cells of the line. We know exactly there's only one
    //cell, so, we don't have to call RenderHLine().
    incr  = 1;
    if(dx == 0)
    {
        int ex = x1 >> cPolySubpixelShift;
        int two_fx = (x1 - (ex << cPolySubpixelShift)) << 1;
        int area;

        first = cPolySubpixelScale;
        if(dy < 0)
        {
            first = 0;
            incr  = -1;
        }

        x_from = x1;

        //RenderHLine(ey1, x_from, fy1, x_from, first);
        delta = first - fy1;
        mCurCell.mCover += delta;
        mCurCell.mArea  += two_fx * delta;

        ey1 += incr;
        SetCurCell(ex, ey1);

        delta = first + first - cPolySubpixelScale;
        area = two_fx * delta;
        while(ey1 != ey2)
        {
            //RenderHLine(ey1, x_from, cPolySubpixelScale - first, x_from, first);
            mCurCell.mCover = delta;
            mCurCell.mArea  = area;
            ey1 += incr;
            SetCurCell(ex, ey1);
        }
        //RenderHLine(ey1, x_from, cPolySubpixelScale - first, x_from, fy2);
        delta = fy2 - cPolySubpixelScale + first;
        mCurCell.mCover += delta;
        mCurCell.mArea  += two_fx * delta;
        return;
    }

    //ok, we have to render several hlines
    p     = (cPolySubpixelScale - fy1) * dx;
    first = cPolySubpixelScale;

    if(dy < 0)
    {
        p     = fy1 * dx;
        first = 0;
        incr  = -1;
        dy    = -dy;
    }

    delta = p / dy;
    mod   = p % dy;

    if(mod < 0)
    {
        delta--;
        mod += dy;
    }

    x_from = x1 + delta;
    RenderHLine(ey1, x1, fy1, x_from, first);

    ey1 += incr;
    SetCurCell(x_from >> cPolySubpixelShift, ey1);

    if(ey1 != ey2)
    {
        p     = cPolySubpixelScale * dx;
        lift  = p / dy;
        rem   = p % dy;

        if(rem < 0)
        {
            lift--;
            rem += dy;
        }
        mod -= dy;

        while(ey1 != ey2)
        {
            delta = lift;
            mod  += rem;
            if (mod >= 0)
            {
                mod -= dy;
                delta++;
            }

            x_to = x_from + delta;
            RenderHLine(ey1, x_from, cPolySubpixelScale - first, x_to, first);
            x_from = x_to;

            ey1 += incr;
            SetCurCell(x_from >> cPolySubpixelShift, ey1);
        }
    }
    RenderHLine(ey1, x_from, cPolySubpixelScale - first, x2, fy2);
}

template<typename tCell>
void CCellRasterizer<tCell>::AllocateBlock()
{
    if(mNextBlock>=mBlocks.size())
        mBlocks.emplace_back(new tCell[cCellBlockSize]);
    mCurCellPtr = mBlocks[mNextBlock++];
}

struct ACellLess
{
    template<typename tCell>
    bool operator()(tCell *p1,tCell *p2)
    {
        return p1->x<p2->x;
    }
};

template<typename tCell>
void CCellRasterizer<tCell>::SortCells()
{
    if(mSorted) return; //Perform sort only the first time.

    AddCurCell();
    mCurCell.x     = 0x7FFFFFFF;
    mCurCell.y     = 0x7FFFFFFF;
    mCurCell.mCover = 0;
    mCurCell.mArea  = 0;

    if(mNumCells == 0)
    {
        mMinY=0x7FFFFFFF;
        mMaxY=-0x7FFFFFFF;
        return;
    }

    // Allocate the array of cell pointers
    mSortedCells.resize(mNumCells);

    // Allocate and zero the Y array
    mSortedY.resize(mMaxY - mMinY + 1);
    for(int i=0;i<mSortedY.size();i++)
    {
        mSortedY[i].mNum=0;
        mSortedY[i].mStart=0;
    }
    for(int i=0;i<mSortedY.size();i++)
    {
        mSortedY[i]={0,0};
    }

    // Create the Y-histogram (count the numbers of cells for each Y)
    tCell** lBlockPtr = mBlocks.data();
    tCell*  lCellPtr;
    unsigned nb = mNumCells >> cCellBlockShift;
    unsigned i;
    while(nb--)
    {
        lCellPtr = *lBlockPtr++;
        i = cCellBlockSize;
        while(i--)
        {
            mSortedY[lCellPtr->y - mMinY].mStart++;
            ++lCellPtr;
        }
    }

    lCellPtr = *lBlockPtr++;
    i = mNumCells & cCellBlockMask;
    while(i--)
    {
        mSortedY[lCellPtr->y - mMinY].mStart++;
        ++lCellPtr;
    }

    // Convert the Y-histogram into the array of starting indexes
    unsigned lStart = 0;
    for(i = 0; i < mSortedY.size(); i++)
    {
        unsigned v = mSortedY[i].mStart;
        mSortedY[i].mStart = lStart;
        lStart += v;
    }

    // Fill the cell pointer array sorted by Y
    lBlockPtr = mBlocks.data();
    nb = mNumCells >> cCellBlockShift;
    while(nb--)
    {
        lCellPtr = *lBlockPtr++;
        i = cCellBlockSize;
        while(i--)
        {
            SSortedY& curr_y = mSortedY[lCellPtr->y - mMinY];
            mSortedCells[curr_y.mStart + curr_y.mNum] = lCellPtr;
            ++curr_y.mNum;
            ++lCellPtr;
        }
    }

    lCellPtr = *lBlockPtr++;
    i = mNumCells & cCellBlockMask;
    while(i--)
    {
        SSortedY& curr_y = mSortedY[lCellPtr->y - mMinY];
        mSortedCells[curr_y.mStart + curr_y.mNum] = lCellPtr;
        ++curr_y.mNum;
        ++lCellPtr;
    }

    // Finally arrange the X-arrays
    for(i = 0; i < mSortedY.size(); i++)
    {
        const SSortedY& curr_y = mSortedY[i];
        if(curr_y.mNum)
        {
            std::sort(mSortedCells.begin()+curr_y.mStart,mSortedCells.begin()+curr_y.mStart+curr_y.mNum,ACellLess());
        }
    }
    mSorted = true;
}


#if 0
    //------------------------------------------------------scanline_hit_test
    class scanline_hit_test
    {
    public:
        scanline_hit_test(int x) : m_x(x), m_hit(false) {}

        void reset_spans() {}
        void finalize(int) {}
        void add_cell(int x, int)
        {
            if(m_x == x) m_hit = true;
        }
        void add_span(int x, int len, int)
        {
            if(m_x >= x && m_x < x+len) m_hit = true;
        }
        unsigned num_spans() const { return 1; }
        bool hit() const { return m_hit; }

    private:
        int  m_x;
        bool m_hit;
    };
#endif

/*namespace image*/ } /*namespace buola*/ }

#endif
